package com.dyz.topics.dynamicProgramming;

public class CanPartition416 {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        //求和
        int sum = 0;
        for(int i =0; i<len; i++){
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        int target = sum/2;
        //动态转移矩阵
        boolean [][] dp = new boolean[len][target+1];
        //初始状态
        if(nums[0]<=target){
            dp[0][nums[0]] = true;
        }
        for(int i=1;i<len; i++){
            for(int j=0; j<=target; j++){
                //不选nums[i]
                dp[i][j] = dp[i-1][j];
                if(nums[i]==target){
                    dp[i][j]=true;
                    continue;
                }
                if(nums[i]<j){
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]];
                }
            }
            //有个值正好一半的时候
            if(dp[i][target]){
                return true;
            }
        }
        return dp[len-1][target];
    }
}
